This is a randomized, double-blind, placebo-controlled study in patients with HIV-associated weight loss. Eligible individuals will receive nandrolone decanoate or placebo by weekly intramuscular injection for 12 weeks. All patients who successfully complete a 12-week placebo-controlled phase will be eligible to receive open-label nandrolone for an additional 12 weeks. Response to treatment will be evaluated by measuring body weight and composition, functional performance, quality of life, and energy and macronutrient intake. Safety, HIV disease progression, and immunologic status will be closely monitored throughout the study.